1704E - Count Seconds - CodeForces Solution


brute force constructive algorithms dp graphs

Please click on ads to support us..

Python Code:

from functools import lru_cache
import sys
import io
import os


MOD = 998244353  
sys.setrecursionlimit(5000)

def main():
    for _ in range(read_int()):
        n, m = read_int_tuple()
        a = read_int_list()
        rg = [[] for _ in range(n)]
        ss = set(range(n))

        for _ in range(m):
            u, v = read_int_tuple()
            rg[v - 1].append(u - 1)
            ss.discard(u - 1)
        
        @lru_cache(None)
        def dfs(u):
            r = a[u]
            s, e = 1, a[u]
            book = []
            for v in rg[u]:
                last, end = dfs(v)
                if last == 0:
                    continue
                book.append((end - last + 2, end + 1))
            book.sort()
            
            for vs, ve in book:
                if vs > e:
                    s, e = ve - (ve - vs + 1 + e - s + 1) + 1, ve
                else:
                    e += ve - vs + 1
            return e - s + 1, e
            
            
        print(dfs(ss.pop())[1] % MOD)
        
        
        

def input(): return sys.stdin.readline().rstrip('\r\n')


def read_int_list():
    return list(map(int, input().split()))


def read_int_tuple():
    return tuple(map(int, input().split()))


def read_int():
    return int(input())



if __name__ == "__main__":
    main()


Comments

Submit
0 Comments
More Questions

1399A - Remove Smallest
208A - Dubstep
1581A - CQXYM Count Permutations
337A - Puzzles
495A - Digital Counter
796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings
677A - Vanya and Fence
1621A - Stable Arrangement of Rooks
472A - Design Tutorial Learn from Math
1368A - C+=
450A - Jzzhu and Children
546A - Soldier and Bananas
32B - Borze
1651B - Prove Him Wrong
381A - Sereja and Dima
41A - Translation
1559A - Mocha and Math
832A - Sasha and Sticks
292B - Network Topology
1339A - Filling Diamonds
910A - The Way to Home
617A - Elephant
48A - Rock-paper-scissors
294A - Shaass and Oskols